# 递归
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        def Traversal(left, right):
            if left is None and right is None:
                return True
            elif left and right and left.val == right.val:
                return Traversal(left.left, right.right) and Traversal(left.right, right.left)
            else:
                return False
        # 递归的起点！
        return Traversal(pRoot.left, pRoot.right)
# 深度优先、广度优先
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        stack =[]
        stack.append(pRoot.right)
        stack.append(pRoot.left)
        while stack!=[]:
            right = stack.pop(0)
            left = stack.pop(0)
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            stack.append(right.right)
            stack.append(left.left)
            stack.append(left.right)
            stack.append(right.left)
        return True